package main.leetcode.primary.from101to200;

import main.datastruc.TreeNode;

/**
 * 105.从前序与中序遍历序列构造二叉树
 *
 * <p>根据一棵树的前序遍历与中序遍历构造二叉树。
 *
 * <p>注意: 你可以假设树中没有重复的元素。
 *
 * <p>来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class ex105 {
    public static void main(String[] args) {
        int[] preorder = {3, 9, 20, 15, 7};
        int[] inorder = {9, 3, 15, 20, 7};
        System.out.println(new ex105().buildTree(preorder, inorder));
    }

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int n = preorder.length;
        if (n < 1) {
            return null;
        }
        return buildTree(preorder, 0, n - 1, inorder, 0, n - 1);
    }

    public TreeNode buildTree(
            int[] preorder, int start1, int end1, int[] inorder, int start2, int end2) {
        if (start1 > end1 || start2 > end2) return null;
        TreeNode root = new TreeNode(preorder[start1]);
        int index = 0;
        for (int i = start2; i <= end2; ++i) {
            if (inorder[i] == preorder[start1]) {
                index = i;
                break;
            }
        }
        root.left =
                buildTree(
                        preorder, start1 + 1, start1 + index - start2, inorder, start2, index - 1);
        root.right =
                buildTree(preorder, start1 + index - start2 + 1, end1, inorder, index + 1, end2);
        return root;
    }
}
